package week12.EXP3;

import week12.EXP3.cn.edu.besti.cs1723.TCM2319.Searching;
import week12.EXP3.cn.edu.besti.cs1723.TCM2319.Sorting;

import java.util.Random;

public class Searching_and_Sorting_Test_2319 {
    public static void main(String[] args) {
        System.out.println("Searching_Test:   ");
        Comparable linearsearch[] = new Comparable[]{1,3,6,9,12,11,2319,4};
        //  线性查找测试 - Exp3 - 1
        System.out.println("线性查找测试 - Exp3 - 1:");
        System.out.println("待查找的数据为： ");
        for(Comparable c : linearsearch){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.println("正常情况：  " );
        System.out.println("查找3的结果为：  "+  Searching.linearSearch(linearsearch,3));
        System.out.println("查找6的结果为：  "+  Searching.linearSearch(linearsearch,6));
        System.out.println("查找9的结果为：  "+  Searching.linearSearch(linearsearch,9));
        System.out.println("查找12的结果为：  "+  Searching.linearSearch(linearsearch,12));
        System.out.println();
        System.out.println("异常情况：  ");
        System.out.println("查找200的结果为：  "+  Searching.linearSearch(linearsearch,200));
        System.out.println("查找1560的结果为：  "+  Searching.linearSearch(linearsearch,1560));
        System.out.println("查找12321的结果为：  "+  Searching.linearSearch(linearsearch,12321));
        System.out.println("查找237704的结果为：  "+  Searching.linearSearch(linearsearch,237704));
        System.out.println();
        System.out.println("边界情况:   ");
        System.out.println("查找1的结果为：  "+  Searching.linearSearch(linearsearch,1));
        System.out.println("查找4的结果为：  "+  Searching.linearSearch(linearsearch,4));
        System.out.println();
        System.out.println();
        System.out.println();
        /**
         * 二分查找的测试 - Exp3 - 3
         */
        System.out.println("二分查找非递归版本 - Exp3 - 3：   ");
        Comparable binarysearch[] = new Comparable[]{1,3,4,6,9,11,12,2319};
        System.out.println("待查找的数据为： ");
        for(Comparable c : binarysearch){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("正常情况：  " );
        System.out.println("查找4的结果为：  "+  Searching.BinarySearch_non_recursion(binarysearch,4));
        System.out.print("异常情况：  ");
        System.out.println("查找100的结果为：  "+  Searching.BinarySearch_non_recursion(binarysearch,100));
        System.out.print("边界情况:   ");
        System.out.println("查找1的结果为：  "+  Searching.BinarySearch_non_recursion(binarysearch,1));
        System.out.println("查找2319的结果为：  "+  Searching.BinarySearch_non_recursion(binarysearch,2319));
        System.out.println();
        System.out.println();
        System.out.println("二分查找递归版本 - Exp3 - 3：   ");
        System.out.println("待查找的数据为： ");
        binarysearch = new Comparable[]{5,8,40,67,91,121,126,2319};
        for(Comparable c : binarysearch){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("正常情况：  " );
        System.out.println("查找126的结果为：  "+  Searching.BinarySearch_recursion(binarysearch,0,binarysearch.length-1,126));
        System.out.print("异常情况：  ");
        System.out.println("查找300的结果为：  "+  Searching.BinarySearch_recursion(binarysearch,0,binarysearch.length-1,300));
        System.out.print("边界情况:   ");
        System.out.println("查找5的结果为：  "+  Searching.BinarySearch_recursion(binarysearch,0,binarysearch.length-1,5));
        System.out.println("查找2319的结果为：  "+  Searching.BinarySearch_recursion(binarysearch,0,binarysearch.length-1,2319));
        System.out.println();
        System.out.println();
        System.out.println();
        /**
         * 插值查找的测试 - Exp3 - 3
         */
        System.out.println("插值查找的测试 - Exp3 - 3：   ");
        int insertionsearch[] = new int[]{2,5,7,9,88,110,126,2319};
        System.out.println("待查找的数据为： ");
        for(int c : insertionsearch){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("正常情况：  " );
        System.out.println("查找126的结果为：  "+  Searching.InsertionSearch(insertionsearch,0,insertionsearch.length-1,126));
        System.out.print("异常情况：  ");
        System.out.println("查找300的结果为：  "+  Searching.InsertionSearch(insertionsearch,0,insertionsearch.length-1,300));
        System.out.print("边界情况:   ");
        System.out.println("查找2的结果为：  "+  Searching.InsertionSearch(insertionsearch,0,insertionsearch.length-1,2));
        System.out.println("查找2319的结果为：  "+  Searching.InsertionSearch(insertionsearch,0,insertionsearch.length-1,2319));
        System.out.println();
        System.out.println();
        System.out.println();
        /**
         * 斐波那契查找 - Exp3 - 3
         */
        System.out.println("斐波那契查找的测试 - Exp3 - 3：   ");
        int FibonacciSearch[] = new int[]{3,5,6,11,16,19,828,2319};
        System.out.println("待查找的数据为： ");
        for(int c : FibonacciSearch){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("正常情况：  " );
        System.out.println("查找828的结果为：  "+  Searching.FibonacciSearch.FibonacciSearch(FibonacciSearch,828));
        System.out.print("异常情况：  ");
        System.out.println("查找320的结果为：  "+  Searching.FibonacciSearch.FibonacciSearch(FibonacciSearch,320));
        System.out.print("边界情况:   ");
        System.out.println("查找3的结果为：  "+  Searching.FibonacciSearch.FibonacciSearch(FibonacciSearch,3));
        System.out.println("查找2319的结果为：  "+  Searching.FibonacciSearch.FibonacciSearch(FibonacciSearch,2319));
        System.out.println();
        System.out.println();
        System.out.println();
        /**
         * 树表查找 - Exp3 - 3
         */
        System.out.println("树表查找的测试 - Exp3 - 3：   ");
        int Tree_table_lookup[] = new int[]{6,8,7,131,1116,129,8428,2319};
        System.out.println("待查找的数据为： ");
        for(int c : Tree_table_lookup){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("正常情况：  " );
        System.out.println("查找8428的结果为：  "+  Searching.Tree_table_lookup(Tree_table_lookup,8428));
        System.out.print("异常情况：  ");
        System.out.println("查找320的结果为：  "+  Searching.Tree_table_lookup(Tree_table_lookup,320));
        System.out.print("边界情况:   ");
        System.out.println("查找6的结果为：  "+  Searching.Tree_table_lookup(Tree_table_lookup,6));
        System.out.println("查找2319的结果为：  "+  Searching.Tree_table_lookup(Tree_table_lookup,2319));
        System.out.println();
        System.out.println();
        System.out.println();
        /**
         * 分块查找 - Exp3 - 3
         */
        System.out.println("分块查找的测试 - Exp3 - 3：   ");
        int index[]={0,22,48,2319};
        int BlockSearch[] = new int[]{22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48, 60, 58, 2319, 49, 86, 53};
        Searching.BlockSearch blockSearch = new Searching.BlockSearch(index);
        System.out.println("待查找的数据为： ");
        for(int c : BlockSearch){
            System.out.print(c + " ");
        }
        System.out.println();
        Searching.BlockSearch.insert(22);
        Searching.BlockSearch.insert(12);
        Searching.BlockSearch.insert(13);
        Searching.BlockSearch.insert(8);
        Searching.BlockSearch.insert(9);
        Searching.BlockSearch.insert(20);
        Searching.BlockSearch.insert(33);
        Searching.BlockSearch.insert(42);
        Searching.BlockSearch.insert(44);
        Searching.BlockSearch.insert(38);
        Searching.BlockSearch.insert(24);
        Searching.BlockSearch.insert(48);
        Searching.BlockSearch.insert(60);
        Searching.BlockSearch.insert(58);
        Searching.BlockSearch.insert(2319);
        Searching.BlockSearch.insert(49);
        Searching.BlockSearch.insert(86);
        Searching.BlockSearch.insert(53);
        System.out.println("对其分块后：");
        Searching.BlockSearch.printAll();
        System.out.print("正常情况：  " );
        System.out.println("查找13的结果为：  "+  Searching.BlockSearch.search(13));
        System.out.print("异常情况：  ");
        System.out.println("查找820的结果为：  "+  Searching.BlockSearch.search(820));
        System.out.print("边界情况:   ");
        System.out.println("查找22的结果为：  "+  Searching.BlockSearch.search(22));
        System.out.println("查找53的结果为：  "+  Searching.BlockSearch.search(53));
        System.out.println();
        System.out.println();
        System.out.println();
        /**
         * 哈希查找 - Exp3 - 3
         */
        System.out.println("哈希查找的测试 - Exp3 - 3：   ");
        int HashSearch[] = new int[]{32, 48, 60, 58, 2319, 49, 86, 53};
        int HashMap[] = new int[13];
        System.out.println("待查找的数据为： ");
        for(int c : HashSearch){
            System.out.print(c + " ");
        }
        System.out.println();
        Searching.Hashinsert(HashMap,11,32);
        Searching.Hashinsert(HashMap,11,48);
        Searching.Hashinsert(HashMap,11,60);
        Searching.Hashinsert(HashMap,11,58);
        Searching.Hashinsert(HashMap,11,2319);
        Searching.Hashinsert(HashMap,11,49);
        Searching.Hashinsert(HashMap,11,86);
        Searching.Hashinsert(HashMap,11,43);
        System.out.print("正常情况：  " );
        System.out.println("查找60的结果为：  "+  Searching.HashSearching(HashMap,11,60));
        System.out.print("异常情况：  ");
        System.out.println("查找872的结果为：  "+  Searching.HashSearching(HashMap,11,872));
        System.out.print("边界情况:   ");
        System.out.println("查找32的结果为：  "+  Searching.HashSearching(HashMap,11,32));
        System.out.println("查找43的结果为：  "+  Searching.HashSearching(HashMap,11,43));
        System.out.println();
        System.out.println();
        System.out.println();






        /**
         * 排序测试
         **/
        System.out.println("Sorting_Test:   ");
        //  选择排序测试
        System.out.println("选择排序测试Exp3-1");
        System.out.println("正常情况：  " );
        int []comparable = new int[]{1,3,6,9,12,11,2319,4};
        System.out.println("原测试用例顺序为：");
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后为：    ");
        Sorting.selectionSort(comparable);
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();

        comparable = new int[]{1,12,11,3,6,9,2319,4};
        System.out.println("原测试用例顺序为：");
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后为：    ");
        Sorting.selectionSort(comparable);
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.println("异常情况：  ");
        comparable = new int[]{1,3,6,9,12,11,2319,4};
        System.out.println("原测试用例顺序为：");
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后为：    ");
        Sorting.selectionSort(comparable);
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();
        comparable = new int[]{1,12,11,3,6,9,2319,4,12,11,3,6,9};
        System.out.println("原测试用例顺序为：");
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后为：    ");
        Sorting.selectionSort(comparable);
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();



        System.out.println("边界情况:   ");
        comparable = new int[]{1,3,6,9,12,2981090,11,2319,4};
        System.out.println("原测试用例顺序为：");
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后为：    ");
        Sorting.selectionSort(comparable);
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();
        comparable = new int[]{-179847841,1,12,11,3,6,9,2319,4};
        System.out.println("原测试用例顺序为：");
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后为：    ");
        Sorting.selectionSort(comparable);
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();





        System.out.println("正序情况：  ");
        comparable = new int[]{1,3,4,6,9,11,12,23,2319};
        System.out.println("原测试用例顺序为：");
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后为：    ");
        Sorting.selectionSort(comparable);
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();
        comparable = new int[]{0,2,4,6,8,10};
        System.out.println("原测试用例顺序为：");
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后为：    ");
        Sorting.selectionSort(comparable);
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();


        System.out.println("逆序情况:   ");
        comparable = new int[]{2319,12,11,9,6,4,3,1};
        System.out.println("原测试用例顺序为：");
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后为：    ");
        Sorting.selectionSort(comparable);
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();
        comparable = new int[]{10,8,6,4,2,0};
        System.out.println("原测试用例顺序为：");
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后为：    ");
        Sorting.selectionSort(comparable);
        for(Comparable c : comparable){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.println();
        System.out.println();
        /**
         * 希尔排序测试Exp3-4
         */
        System.out.println("希尔排序测试Exp3-4:  ");
        System.out.println("正常情况：");
        int Shell_Sort[] = new int[]{32, 48, 60, 58, 2319, 49, 86, 53};
        System.out.println("待排序数组：");
        for(int c : Shell_Sort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("希尔排序后："+ Sorting.Shell_Sort(Shell_Sort) );
        System.out.println("异常情况：");
        Shell_Sort = new int[]{32, 48,23, 60, 58, 1,3,4,6,55,22,2319, 49,23, 86, 53};
        System.out.println("待排序数组：");
        for(int c : Shell_Sort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("希尔排序后："+ Sorting.Shell_Sort(Shell_Sort) );
        System.out.println("边界情况：");
        Shell_Sort = new int[]{32, 48, 60, 58, -2319, 49, 86, 532133};
        System.out.println("待排序数组：");
        for(int c : Shell_Sort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("希尔排序后："+ Sorting.Shell_Sort(Shell_Sort) );
        System.out.println();
        System.out.println();
        System.out.println();

        /**
         * 排序测试Exp3-4
         */
        System.out.println("堆排序测试Exp3-4:  ");
        System.out.println("正常情况：");
        int Heap_Sort[] = new int[]{36, 30, 18, 40,32,45, 22, 50, 2319};
        System.out.println("待排序数组：");
        for(int c : Heap_Sort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("堆排序后："+ Sorting.HeapSort(Heap_Sort) );
        System.out.println("异常情况：");
        Heap_Sort = new int[]{32, 4,3, 0, 5, 22,2319, 49,5,2,4,23, 86, 53};
        System.out.println("待排序数组：");
        for(int c : Heap_Sort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("堆排序后："+ Sorting.HeapSort(Heap_Sort) );
        System.out.println("边界情况：");
        Heap_Sort = new int[]{32, -2837848, 0, 58, 2319, 49, 86, 532342133};
        System.out.println("待排序数组：");
        for(int c : Heap_Sort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("堆排序后："+ Sorting.HeapSort(Heap_Sort) );
        System.out.println();
        System.out.println();
        System.out.println();
        /**
         * 二叉树排序测试Exp3-4
         */
        System.out.println("二叉树排序测试Exp3-4:  ");
        System.out.println("正常情况：");
        int Binary_tree_sort[] = new int[]{32, 14, 18, 420,3,5, 22, 0, 2319};
        System.out.println("待排序数组：");
        for(int c : Binary_tree_sort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("二叉树排序后："+ Sorting.Binarytree_sort(Binary_tree_sort));
        System.out.println("异常情况：");
        Binary_tree_sort = new int[]{32, 44,34, 0, 54, 212,2319, 49,54,2,44,23, 86, 53};
        System.out.println("待排序数组：");
        for(int c : Binary_tree_sort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("二叉树排序后："+ Sorting.Binarytree_sort(Binary_tree_sort));
        System.out.println("边界情况：");
        Binary_tree_sort = new int[]{302, -2837848, 0, 518, 2319, 4924, 186, 532342133};
        System.out.println("待排序数组：");
        for(int c : Binary_tree_sort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("二叉树排序后："+ Sorting.Binarytree_sort(Binary_tree_sort) );
        System.out.println();
        System.out.println();
        System.out.println();
        /**
         * 插入排序测试Exp3-4
         */
        System.out.println("插入排序测试Exp3-4:  ");
        System.out.println("正常情况：");
        int insert_sort[] = new int[]{3, 124, 1, 40,31,54, 22, 0, 2319};
        System.out.println("待排序数组：");
        for(int c : insert_sort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("插入排序后："+ Sorting.insertionSort(insert_sort));
        System.out.println("异常情况：");
        insert_sort = new int[]{33, 44,3, 0, 4, 12,2319, 49,54,2,44,23, 86, 53};
        System.out.println("待排序数组：");
        for(int c : insert_sort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("插入排序后："+ Sorting.insertionSort(insert_sort));
        System.out.println("边界情况：");
        insert_sort = new int[]{30, -2848, 0, 518, 2319, 4924, 1286, 532133};
        System.out.println("待排序数组：");
        for(int c : insert_sort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("插入排序后："+ Sorting.insertionSort(insert_sort));
        System.out.println();
        System.out.println();
        System.out.println();
        /**
         * 冒泡排序测试Exp3-4
         */
        System.out.println("冒泡排序测试Exp3-4:  ");
        System.out.println("正常情况：");
        int bubble_sort[] = new int[]{3, 14, 4,1,5, 2, 0, 2319};
        System.out.println("待排序数组：");
        for(int c : bubble_sort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("冒泡排序后："+ Sorting.bubbleSort(bubble_sort));
        System.out.println("异常情况：");
        bubble_sort = new int[]{323, 4,3, 1, 4, 12,2319, 49,54,2,44,323, 8, 53};
        System.out.println("待排序数组：");
        for(int c : bubble_sort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("冒泡排序后："+ Sorting.bubbleSort(bubble_sort));
        System.out.println("边界情况：");
        bubble_sort = new int[]{30, -223848, 0, 518, 2319, 4, 12, 533};
        System.out.println("待排序数组：");
        for(int c : bubble_sort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("冒泡排序后："+ Sorting.bubbleSort(bubble_sort));
        System.out.println();
        System.out.println();
        System.out.println();
        /**
         * 归并排序测试Exp3-4
         */
        System.out.println("归并排序测试Exp3-4:  ");
        System.out.println("正常情况：");
        int mergeSort[] = new int[]{13, 134, 41,12,55, 2, 0, 2319};
        System.out.println("待排序数组：");
        for(int c : mergeSort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后："+ Sorting.mergeSort(mergeSort));
        System.out.println("异常情况：");
        mergeSort = new int[]{3323, 244,3, 1, 244, 12,2319, 419,5244,25,44,3323, 8, 53};
        System.out.println("待排序数组：");
        for(int c : mergeSort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后："+ Sorting.mergeSort(mergeSort));
        System.out.println("边界情况：");
        mergeSort = new int[]{30, -248, 0, 5128, 2319, 4, 12, 53131};
        System.out.println("待排序数组：");
        for(int c : mergeSort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后："+ Sorting.mergeSort(mergeSort));
        System.out.println();
        System.out.println();
        System.out.println();
        /**
         * 快速排序测试Exp3-4
         */
        System.out.println("快速排序测试Exp3-4:  ");
        System.out.println("正常情况：");
        int quickSort[] = new int[]{3, 14, 41,122,535, 2, 0, 2319};
        System.out.println("待排序数组：");
        for(int c : quickSort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后："+ Sorting.quickSort(quickSort));
        System.out.println("异常情况：");
        quickSort = new int[]{3, 24,3, 1, 24, 122,2319, 19,44,5,44,23, 8, 53};
        System.out.println("待排序数组：");
        for(int c : quickSort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后："+ Sorting.quickSort(quickSort));
        System.out.println("边界情况：");
        quickSort = new int[]{30, -2231248, 0, 128, 2319, 4, 12, 53421131};
        System.out.println("待排序数组：");
        for(int c : quickSort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后："+ Sorting.quickSort(quickSort));
        System.out.println();
        System.out.println();
        System.out.println();
        /**
         * 间隔排序测试Exp3-4
         */
        System.out.println("间隔(冒泡排序变异算法)排序测试Exp3-4:  ");
        System.out.println("正常情况：");
        int gapSort[] = new int[]{233, 1244, 41,122312,535, 12, 40, 2319};
        System.out.println("待排序数组：");
        for(int c : gapSort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后："+ Sorting.gapSort(gapSort,3));
        System.out.println("异常情况：");
        gapSort = new int[]{3, 24,3, 11, 2319, 19,44,5,44,23, 8,153};
        System.out.println("待排序数组：");
        for(int c : gapSort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后："+ Sorting.gapSort(gapSort,4));
        System.out.println("边界情况：");
        gapSort = new int[]{30, -228, 10, 8, 2319, 44, 122, 53421};
        System.out.println("待排序数组：");
        for(int c : gapSort){
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("排序后："+ Sorting.gapSort(gapSort,4));
        System.out.println();
        System.out.println();
        System.out.println();









    }
}
